package com.linyaonan.leetcode.medium._75;

/**
 * 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 *
 * 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 *
 * 必须在不使用库的sort函数的情况下解决这个问题。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [2,0,2,1,1,0]
 * 输出：[0,0,1,1,2,2]
 * 示例 2：
 *
 * 输入：nums = [2,0,1]
 * 输出：[0,1,2]
 *  
 *
 * 提示：
 *
 * n == nums.length
 * 1 <= n <= 300
 * nums[i] 为 0、1 或 2
 *  
 *
 * 进阶：
 *
 * 你可以不使用代码库中的排序函数来解决这道题吗？
 * 你能想出一个仅使用常数空间的一趟扫描算法吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sort-colors
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    /**
     * 思路：
     * 1. 首先数组中只有0,1,2
     * 2. 第一次排序，就把所有的2放到尾部（当前位置与尾部位置交换），如果尾部就为2则不交换，交换后前移，只到两个游标相遇
     * 3. 同理将所有的1放到上次的尾部，只到相遇结束
     * @param nums
     */
    public void sortColors(int[] nums) {
        // 特殊情况则不需要排序
        if (nums == null || nums.length <= 1) {
            return;
        }
        // 确定2的交换位置
        int twoIndex = nums.length - 1;
        int start = 0;

        while (start < twoIndex && twoIndex >= 0) {
            if (nums[twoIndex] == 2) {
                twoIndex--;
                continue;
            } else {
                if (nums[start] == 2) {
                    nums[start] = nums[twoIndex];
                    nums[twoIndex] = 2;
                }
            }
            start++;
        }
        // 特殊边界需要处理下
        if (nums[twoIndex] == 2) {
            twoIndex--;
        }
        int oneIndex = twoIndex;
        // 重置
        start = 0;
        while (start < oneIndex && oneIndex >= 0) {
            if (nums[oneIndex] == 1) {
                oneIndex--;
                continue;
            } else {
                if (nums[start] == 1) {
                    nums[start] = nums[oneIndex];
                    nums[oneIndex] = 1;
                }
            }
            start++;
        }
    }

    /**
     * 还是上面的思路，使用双指针，l指针与r指针，r指针只存放2，l指针就是正常遍历，相遇结束
     * @param nums
     */
    public void sortColors2(int[] nums) {

        if (nums == null || nums.length <= 1) {
            return;
        }
        int twoIndex = nums.length - 1;
        {
            // 1. 先把2全部转移到后面
            int l = 0;
            while (l < twoIndex) {
                int n = nums[l];
                if (n == 2) {
                    // 从后向前找到不是2的索引位置
                    while (twoIndex > l && nums[twoIndex] == 2) {
                        twoIndex--;
                    }
                    nums[l] = nums[twoIndex];
                    nums[twoIndex] = 2;
                    twoIndex--;
                }
                l++;
            }
            while (twoIndex > 0 && nums[twoIndex] == 2) {
                twoIndex--;
            }
        }
        {
            // 2. 再将0,1 进行交换
            int l = 0;
            while (l < twoIndex) {
                int n = nums[l];
                if (n == 1) {
                    while (twoIndex > l && nums[twoIndex] == 1) {
                        twoIndex--;
                    }
                    nums[l] = nums[twoIndex];
                    nums[twoIndex] = 1;
                    twoIndex--;
                }
                l++;
            }
        }

    }
}